package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/15.
 * 连续子数组的最大和
 */
public class MaxSum {

    //动态规划
    public int FindGreatestSumOfSubArray1(int[] arr,int n){
        int sum = arr[0];
        int max = arr[0];
        for (int i = 1; i < n; i++){
            sum = Math.max(sum+arr[i],arr[i]);
            if (sum > max)
                max = sum;
        }
        return max;
    }

    //暴力法
    public int FindGreatestSumOfSubArray2(int[] array){
        if(array == null || (array.length == 1 && array[0] <= 0))
            return 0;
        int cur = array[0];
        int sum = array[0];
        for (int i = 1; i < array.length; i++){
            if (cur < 0)
                cur = 0;
            cur = cur + array[i];
            if (sum <= cur)
                sum = cur;
        }
        return sum;
    }
}
